/*
 * @lc app=leetcode.cn id=869 lang=typescript
 *
 * [869] 重新排序得到 2 的幂
 */

// @lc code=start
function reorderedPowerOf2(n: number): boolean {
  const isValid = (n: number): boolean => {
    return (n & (n - 1)) === 0;
  };

  const backtrack = (nums: string[], idx: number, num: number): boolean => {
    // 得到排列后判断是否满足为2的幂次方
    if (idx === nums.length) {
      return isValid(num);
    }

    // 全排列
    for (let i = 0; i < nums.length; i++) {
      // 不能有前导零
      // 当前位访问过
      if ((num === 0 && nums[i] === '0') || visited[i]) {
        continue;
      }
      visited[i] = 1;
      if (backtrack(nums, idx + 1, num * 10 + Number(nums[i]))) {
        return true;
      }
      visited[i] = 0;
    }

    return false;
  };

  const nums = Array.from(String(n));
  const visited = new Array(nums.length).fill(0);

  return backtrack(nums, 0, 0);
}
// @lc code=end
